{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Time to Cross a Bridge"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #simulation #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #模拟 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findCrossingTime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #过桥的时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>共有 <code>k</code> 位工人计划将 <code>n</code> 个箱子从旧仓库移动到新仓库。给你两个整数 <code>n</code> 和 <code>k</code>，以及一个二维整数数组 <code>time</code> ，数组的大小为 <code>k x 4</code> ，其中 <code>time[i] = [leftToRight<sub>i</sub>, pickOld<sub>i</sub>, rightToLeft<sub>i</sub>, putNew<sub>i</sub>]</code> 。</p>\n",
    "\n",
    "<p>一条河将两座仓库分隔，只能通过一座桥通行。旧仓库位于河的右岸，新仓库在河的左岸。开始时，所有 <code>k</code> 位工人都在桥的左侧等待。为了移动这些箱子，第 <code>i</code> 位工人（下标从 <strong>0</strong> 开始）可以：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>从左岸（新仓库）跨过桥到右岸（旧仓库），用时 <code>leftToRight<sub>i</sub></code> 分钟。</li>\n",
    "\t<li>从旧仓库选择一个箱子，并返回到桥边，用时 <code>pickOld<sub>i</sub></code> 分钟。不同工人可以同时搬起所选的箱子。</li>\n",
    "\t<li>从右岸（旧仓库）跨过桥到左岸（新仓库），用时 <code>rightToLeft<sub>i</sub></code> 分钟。</li>\n",
    "\t<li>将箱子放入新仓库，并返回到桥边，用时 <code>putNew<sub>i</sub></code> 分钟。不同工人可以同时放下所选的箱子。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果满足下面任一条件，则认为工人 <code>i</code> 的 <strong>效率低于</strong> 工人 <code>j</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>leftToRight<sub>i</sub> + rightToLeft<sub>i</sub> &gt; leftToRight<sub>j</sub> + rightToLeft<sub>j</sub></code></li>\n",
    "\t<li><code>leftToRight<sub>i</sub> + rightToLeft<sub>i</sub> == leftToRight<sub>j</sub> + rightToLeft<sub>j</sub></code> 且 <code>i &gt; j</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>工人通过桥时需要遵循以下规则：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果工人 <code>x</code> 到达桥边时，工人 <code>y</code> 正在过桥，那么工人 <code>x</code> 需要在桥边等待。</li>\n",
    "\t<li>如果没有正在过桥的工人，那么在桥右边等待的工人可以先过桥。如果同时有多个工人在右边等待，那么 <strong>效率最低</strong> 的工人会先过桥。</li>\n",
    "\t<li>如果没有正在过桥的工人，且桥右边也没有在等待的工人，同时旧仓库还剩下至少一个箱子需要搬运，此时在桥左边的工人可以过桥。如果同时有多个工人在左边等待，那么 <strong>效率最低</strong> 的工人会先过桥。</li>\n",
    "</ul>\n",
    "\n",
    "<p>所有 <code>n</code> 个盒子都需要放入新仓库，<span class=\"text-only\" data-eleid=\"8\" style=\"white-space: pre;\">请你返回最后一个搬运箱子的工人 </span><strong><span class=\"text-only\" data-eleid=\"9\" style=\"white-space: pre;\">到达河左岸</span></strong><span class=\"text-only\" data-eleid=\"10\" style=\"white-space: pre;\"> 的时间。</span></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1, k = 3, time = [[1,1,2,1],[1,1,3,1],[1,1,4,1]]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>\n",
    "从 0 到 1 ：工人 2 从左岸过桥到达右岸。\n",
    "从 1 到 2 ：工人 2 从旧仓库搬起一个箱子。\n",
    "从 2 到 6 ：工人 2 从右岸过桥到达左岸。\n",
    "从 6 到 7 ：工人 2 将箱子放入新仓库。\n",
    "整个过程在 7 分钟后结束。因为问题关注的是最后一个工人到达左岸的时间，所以返回 6 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, k = 2, time = [[1,9,1,8],[10,10,10,10]]\n",
    "<strong>输出：</strong>50\n",
    "<strong>解释：</strong>\n",
    "从 0 到 10 ：工人 1 从左岸过桥到达右岸。\n",
    "从 10 到 20 ：工人 1 从旧仓库搬起一个箱子。\n",
    "从 10 到 11 ：工人 0 从左岸过桥到达右岸。\n",
    "从 11 到 20 ：工人 0 从旧仓库搬起一个箱子。\n",
    "从 20 到 30 ：工人 1 从右岸过桥到达左岸。\n",
    "从 30 到 40 ：工人 1 将箱子放入新仓库。\n",
    "从 30 到 31 ：工人 0 从右岸过桥到达左岸。\n",
    "从 31 到 39 ：工人 0 将箱子放入新仓库。\n",
    "从 39 到 40 ：工人 0 从左岸过桥到达右岸。\n",
    "从 40 到 49 ：工人 0 从旧仓库搬起一个箱子。\n",
    "从 49 到 50 ：工人 0 从右岸过桥到达左岸。\n",
    "从 50 到 58 ：工人 0 将箱子放入新仓库。\n",
    "整个过程在 58 分钟后结束。因为问题关注的是最后一个工人到达左岸的时间，所以返回 50 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n, k &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>time.length == k</code></li>\n",
    "\t<li><code>time[i].length == 4</code></li>\n",
    "\t<li><code>1 &lt;= leftToRight<sub>i</sub>, pickOld<sub>i</sub>, rightToLeft<sub>i</sub>, putNew<sub>i</sub> &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [time-to-cross-a-bridge](https://leetcode.cn/problems/time-to-cross-a-bridge/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [time-to-cross-a-bridge](https://leetcode.cn/problems/time-to-cross-a-bridge/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1\\n3\\n[[1,1,2,1],[1,1,3,1],[1,1,4,1]]', '3\\n2\\n[[1,9,1,8],[10,10,10,10]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:\n",
    "\n",
    "        def helper(a):\n",
    "            return - (time[a][0] + time[a][2]), -a \n",
    "        \n",
    "        idxs = [i for i in range(len(time))]\n",
    "        idxs.sort(key=helper)\n",
    "        time2 = []\n",
    "        for i in idxs:\n",
    "            time2.append(time[i])\n",
    "        time = time2\n",
    "        \n",
    "        workLeft = []\n",
    "        waitLeft = [i for i in range(len(time))]\n",
    "        waitRight = []\n",
    "        workRight = []\n",
    "\n",
    "        remain = n\n",
    "        curTime = 0\n",
    "\n",
    "        while remain > 0 or waitRight or workRight:\n",
    "            while workRight and workRight[0][0] <= curTime:\n",
    "                t, idx = heapq.heappop(workRight)\n",
    "                heapq.heappush(waitRight, idx)\n",
    "            while workLeft and workLeft[0][0] <= curTime:\n",
    "                t, idx = heapq.heappop(workLeft)\n",
    "                heapq.heappush(waitLeft, idx)\n",
    "            if waitRight:\n",
    "                idx = heapq.heappop(waitRight)\n",
    "                curTime = curTime + time[idx][2]\n",
    "                heapq.heappush(workLeft, (curTime + time[idx][3], idx))\n",
    "            elif remain > 0 and waitLeft:\n",
    "                idx = heapq.heappop(waitLeft)\n",
    "                curTime = curTime + time[idx][0]\n",
    "                heapq.heappush(workRight, (curTime + time[idx][1], idx))\n",
    "                remain -= 1\n",
    "            else:\n",
    "                nxt = sys.maxsize\n",
    "                if workLeft:\n",
    "                    nxt = min(nxt, workLeft[0][0])\n",
    "                if workRight:\n",
    "                    nxt = min(nxt, workRight[0][0])\n",
    "                if nxt != sys.maxsize:\n",
    "                    curTime = max(nxt, curTime)\n",
    "        \n",
    "        return curTime\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:\n",
    "        time.sort(key=lambda x: x[0] + x[2])\n",
    "        cur = 0\n",
    "        wait_in_left, wait_in_right = [], []\n",
    "        work_in_left, work_in_right = [], []\n",
    "        for i in range(k):\n",
    "            heappush(wait_in_left, -i)\n",
    "        while 1:\n",
    "            while work_in_left:\n",
    "                t, i = work_in_left[0]\n",
    "                if t > cur:\n",
    "                    break\n",
    "                heappop(work_in_left)\n",
    "                heappush(wait_in_left, -i)\n",
    "            while work_in_right:\n",
    "                t, i = work_in_right[0]\n",
    "                if t > cur:\n",
    "                    break\n",
    "                heappop(work_in_right)\n",
    "                heappush(wait_in_right, -i)\n",
    "            left_to_go = n > 0 and wait_in_left\n",
    "            right_to_go = bool(wait_in_right)\n",
    "            if not left_to_go and not right_to_go:\n",
    "                nxt = inf\n",
    "                if work_in_left:\n",
    "                    nxt = min(nxt, work_in_left[0][0])\n",
    "                if work_in_right:\n",
    "                    nxt = min(nxt, work_in_right[0][0])\n",
    "                cur = nxt\n",
    "                continue\n",
    "            if right_to_go:\n",
    "                i = -heappop(wait_in_right)\n",
    "                cur += time[i][2]\n",
    "                if n == 0 and not wait_in_right and not work_in_right:\n",
    "                    return cur\n",
    "                heappush(work_in_left, (cur + time[i][3], i))\n",
    "            else:\n",
    "                i = -heappop(wait_in_left)\n",
    "                cur += time[i][0]\n",
    "                n -= 1\n",
    "                heappush(work_in_right, (cur + time[i][1], i))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:\n",
    "        time.sort(key=lambda x: x[0] + x[2])\n",
    "        cur = 0\n",
    "        wait_in_left, wait_in_right = [], []\n",
    "        work_in_left, work_in_right = [], []\n",
    "        for i in range(k):\n",
    "            heappush(wait_in_left, -i)\n",
    "        while 1:\n",
    "            while work_in_left:\n",
    "                t, i = work_in_left[0]\n",
    "                if t > cur:\n",
    "                    break\n",
    "                heappop(work_in_left)\n",
    "                heappush(wait_in_left, -i)\n",
    "            while work_in_right:\n",
    "                t, i = work_in_right[0]\n",
    "                if t > cur:\n",
    "                    break\n",
    "                heappop(work_in_right)\n",
    "                heappush(wait_in_right, -i)\n",
    "            left_to_go = n > 0 and wait_in_left\n",
    "            right_to_go = bool(wait_in_right)\n",
    "            if not left_to_go and not right_to_go:\n",
    "                nxt = inf\n",
    "                if work_in_left:\n",
    "                    nxt = min(nxt, work_in_left[0][0])\n",
    "                if work_in_right:\n",
    "                    nxt = min(nxt, work_in_right[0][0])\n",
    "                cur = nxt\n",
    "                continue\n",
    "            if right_to_go:\n",
    "                i = -heappop(wait_in_right)\n",
    "                cur += time[i][2]\n",
    "                if n == 0 and not wait_in_right and not work_in_right:\n",
    "                    return cur\n",
    "                heappush(work_in_left, (cur + time[i][3], i))\n",
    "            else:\n",
    "                i = -heappop(wait_in_left)\n",
    "                cur += time[i][0]\n",
    "                n -= 1\n",
    "                heappush(work_in_right, (cur + time[i][1], i))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:\n",
    "\n",
    "        # 根据时间进行排序，sort默认值相同时，下标大的放后。\n",
    "\n",
    "        # 根据题目规则，过桥时间相同的下标大的效率低，因此效率低的就会放后。\n",
    "\n",
    "        # 而过桥时间不同的，时间大的效率低。而前面确定了效率低的放后，说明时间大的要放后，因此对时间进行升序排序\n",
    "\n",
    "        # 排序后效率低的编号大，根据下标即可确定工人的效率高低\n",
    "\n",
    "        time.sort(key=lambda t: t[0] + t[2]) \n",
    "        # 初始化\n",
    "        currTime, remain = 0, n\n",
    "        waitLefts = [-i for i in range(k - 1, -1, -1)]    # 初始化左岸等待队列，效率低的优先，因此倒序遍历工人编号。由于进行大顶堆排序需要使用负号进行改变排序方向，因此引入负号\n",
    "        waitRights = []\n",
    "        workLefts = []\n",
    "        workRights = []\n",
    "        # 只要还有剩余箱子或者右岸还有工人，就模拟搬运\n",
    "        while remain > 0 or waitRights or workRights:\n",
    "\n",
    "            # 1. 若 workLeft 或 workRight 中的工人完成工作，则将他们取出，并分别放置到 waitLeft 和 waitRight 中。\n",
    "            while workLefts and workLefts[0][0] <= currTime:\n",
    "\n",
    "                p = heapq.heappop(workLefts)         # 返回一个左岸完成工作的工人, p = [finishTime, i]\n",
    "                heapq.heappush(waitLefts, -p[1])    # 将完成工作的工人加入左岸等待队列，且效率低在堆顶。由于效率低的编号大，因此要实现的是大顶堆，编号之前加入负号实现\n",
    "\n",
    "            while workRights and workRights[0][0] <= currTime:\n",
    "\n",
    "                p = heapq.heappop(workRights)         # 返回一个右岸完成工作的工人, p = [finishTime, i]\n",
    "                heapq.heappush(waitRights, -p[1])    # 将完成工作的工人加入右岸等待队列\n",
    "\n",
    "            if waitRights:\n",
    "\n",
    "                # 2.若右侧有工人在等待，则取出优先级最低的工人并过桥\n",
    "                i = -heapq.heappop(waitRights)\n",
    "                currTime += time[i][2]  #  更新当前时刻，当前时刻 + 右到左的过桥时间\n",
    "                heapq.heappush(workLefts, [currTime + time[i][3], i])   # 右到左的工人完成时间为到达左岸时刻 + 放下箱子的时间\n",
    "\n",
    "            elif remain > 0 and waitLefts:\n",
    "\n",
    "                # 3. 若右侧还有箱子，并且左侧有工人在等待，则取出优先级最低的工人并过桥\n",
    "                i = -heapq.heappop(waitLefts)\n",
    "                currTime += time[i][0]  #  更新当前时刻，当前时刻 + 左到右的过桥时间\n",
    "                heapq.heappush(workRights, [currTime + time[i][1], i])   # 左到右的工人完成时间为到达右岸时刻 + 搬起箱子的时间\n",
    "                remain -= 1     # 过去一个工人剩余箱子数就减1\n",
    "\n",
    "            else:\n",
    "                # 4. 否则，没有人需要过桥，时间过渡到 workLeft 和 workRight 中的最早完成时间\n",
    "                nextTime = sys.maxsize\n",
    "\n",
    "                if workLefts:\n",
    "                    nextTime = min(nextTime, workLefts[0][0])   # 查看workLefts堆顶元素workLefts[0]\n",
    "\n",
    "                if workRights:\n",
    "                    nextTime = min(nextTime, workRights[0][0])  # 查看workRights堆顶元素workRights[0]\n",
    "\n",
    "                if nextTime != sys.maxsize:\n",
    "                    currTime = max(currTime, nextTime)\n",
    "        return currTime\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:\n",
    "        # 根据时间进行排序，sort默认值相同时，下标大的放后。\n",
    "        # 根据题目规则，过桥时间相同的下标大的效率低，因此效率低的就会放后。\n",
    "        # 而过桥时间不同的，时间大的效率低。而前面确定了效率低的放后，说明时间大的要放后，因此对时间进行升序排序\n",
    "        # 排序后效率低的编号大，根据下标即可确定工人的效率高低\n",
    "        time.sort(key=lambda t: t[0] + t[2]) \n",
    "        # 初始化\n",
    "        currTime, remain = 0, n\n",
    "        waitLefts = [-i for i in range(k - 1, -1, -1)]    # 初始化左岸等待队列，效率低的优先，因此倒序遍历工人编号。由于进行大顶堆排序需要使用负号进行改变排序方向，因此引入负号\n",
    "        waitRights = []\n",
    "        workLefts = []\n",
    "        workRights = []\n",
    "        # 只要还有剩余箱子或者右岸还有工人，就模拟搬运\n",
    "        while remain > 0 or waitRights or workRights:\n",
    "            # 1. 若 workLeft 或 workRight 中的工人完成工作，则将他们取出，并分别放置到 waitLeft 和 waitRight 中。\n",
    "            while workLefts and workLefts[0][0] <= currTime:\n",
    "                p = heapq.heappop(workLefts)         # 返回一个左岸完成工作的工人, p = [finishTime, i]\n",
    "                heapq.heappush(waitLefts, -p[1])    # 将完成工作的工人加入左岸等待队列，且效率低在堆顶。由于效率低的编号大，因此要实现的是大顶堆，编号之前加入负号实现\n",
    "            while workRights and workRights[0][0] <= currTime:\n",
    "                p = heapq.heappop(workRights)         # 返回一个右岸完成工作的工人, p = [finishTime, i]\n",
    "                heapq.heappush(waitRights, -p[1])    # 将完成工作的工人加入右岸等待队列\n",
    "            if waitRights:\n",
    "                # 2.若右侧有工人在等待，则取出优先级最低的工人并过桥\n",
    "                i = -heapq.heappop(waitRights)\n",
    "                currTime += time[i][2]  #  更新当前时刻，当前时刻 + 右到左的过桥时间\n",
    "                heapq.heappush(workLefts, [currTime + time[i][3], i])   # 右到左的工人完成时间为到达左岸时刻 + 放下箱子的时间\n",
    "            elif remain > 0 and waitLefts:\n",
    "                # 3. 若右侧还有箱子，并且左侧有工人在等待，则取出优先级最低的工人并过桥\n",
    "                i = -heapq.heappop(waitLefts)\n",
    "                currTime += time[i][0]  #  更新当前时刻，当前时刻 + 左到右的过桥时间\n",
    "                heapq.heappush(workRights, [currTime + time[i][1], i])   # 左到右的工人完成时间为到达右岸时刻 + 搬起箱子的时间\n",
    "                remain -= 1     # 过去一个工人剩余箱子数就减1\n",
    "            else:\n",
    "                # 4. 否则，没有人需要过桥，时间过渡到 workLeft 和 workRight 中的最早完成时间\n",
    "                nextTime = sys.maxsize\n",
    "                if workLefts:\n",
    "                    nextTime = min(nextTime, workLefts[0][0])   # 查看workLefts堆顶元素workLefts[0]\n",
    "                if workRights:\n",
    "                    nextTime = min(nextTime, workRights[0][0])  # 查看workRights堆顶元素workRights[0]\n",
    "                if nextTime != sys.maxsize:\n",
    "                    currTime = max(currTime, nextTime)\n",
    "        return currTime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:\n",
    "        time.sort(key=lambda x: x[0] + x[2])\n",
    "        cur = 0\n",
    "        wait_in_left, wait_in_right = [], []\n",
    "        work_in_left, work_in_right = [], []\n",
    "        for i in range(k):\n",
    "            heappush(wait_in_left, -i)\n",
    "        while 1:\n",
    "            while work_in_left:\n",
    "                t, i = work_in_left[0]\n",
    "                if t > cur:\n",
    "                    break\n",
    "                heappop(work_in_left)\n",
    "                heappush(wait_in_left, -i)\n",
    "            while work_in_right:\n",
    "                t, i = work_in_right[0]\n",
    "                if t > cur:\n",
    "                    break\n",
    "                heappop(work_in_right)\n",
    "                heappush(wait_in_right, -i)\n",
    "            left_to_go = n > 0 and wait_in_left\n",
    "            right_to_go = bool(wait_in_right)\n",
    "            if not left_to_go and not right_to_go:\n",
    "                nxt = inf\n",
    "                if work_in_left:\n",
    "                    nxt = min(nxt, work_in_left[0][0])\n",
    "                if work_in_right:\n",
    "                    nxt = min(nxt, work_in_right[0][0])\n",
    "                cur = nxt\n",
    "                continue\n",
    "            if right_to_go:\n",
    "                i = -heappop(wait_in_right)\n",
    "                cur += time[i][2]\n",
    "                if n == 0 and not wait_in_right and not work_in_right:\n",
    "                    return cur\n",
    "                heappush(work_in_left, (cur + time[i][3], i))\n",
    "            else:\n",
    "                i = -heappop(wait_in_left)\n",
    "                cur += time[i][0]\n",
    "                n -= 1\n",
    "                heappush(work_in_right, (cur + time[i][1], i))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:\n",
    "        time.sort(key = lambda x: x[0]+x[2]) # 效率高的在前，效率低的在后\n",
    "        # left_wait right_wait存下标\n",
    "        # left_work right_work存下标和完成卸货任务准备排队的时刻\n",
    "        # heapq存的是最小堆\n",
    "        # 效率低的索引值大，所以需要对索引求负\n",
    "        left_wait = [-i for i in range(k)]\n",
    "        right_wait = []\n",
    "        left_work = []\n",
    "        right_work = []\n",
    "        heapq.heapify(left_wait)\n",
    "        count = 0\n",
    "        curTime = 0 # 存当前时间\n",
    "        while count<n or right_work or right_wait:\n",
    "            while left_work and left_work[0][0]<=curTime:\n",
    "                _, idx_left = heapq.heappop(left_work)\n",
    "                heapq.heappush(left_wait, -idx_left)\n",
    "            while right_work and right_work[0][0]<=curTime:\n",
    "                _, idx_right = heapq.heappop(right_work)\n",
    "                heapq.heappush(right_wait, -idx_right)\n",
    "            # 若右侧有人排队，就先回\n",
    "            if right_wait:\n",
    "                idx_right = -heapq.heappop(right_wait)\n",
    "                curTime += time[idx_right][2]\n",
    "                # 存完成卸货任务的时刻到left_work\n",
    "                heapq.heappush(left_work, [curTime+time[idx_right][3], idx_right])\n",
    "            # 若右侧没有人回并且count<n\n",
    "            elif left_wait and count<n:\n",
    "                count += 1\n",
    "                idx_left = -heapq.heappop(left_wait)\n",
    "                curTime += time[idx_left][0]\n",
    "                # 存完成装货任务的时刻到right_work\n",
    "                heapq.heappush(right_work, [curTime+time[idx_left][1], idx_left])\n",
    "            # 若右侧没人回并且左侧没人去，就需要找到left_work和right_work的最小值，curTime为curTime和两者最小值的最大值\n",
    "            elif left_work or right_work:\n",
    "                stampTime = float('inf')\n",
    "                if left_work:\n",
    "                    stampTime = min(stampTime, left_work[0][0])\n",
    "                if right_work:\n",
    "                    stampTime = min(stampTime, right_work[0][0])\n",
    "                curTime = max(stampTime, curTime)\n",
    "            else:\n",
    "                continue\n",
    "\n",
    "        return curTime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:\n",
    "        time.sort(key=lambda x: x[0] + x[2])\n",
    "        cur = 0\n",
    "        wait_in_left, wait_in_right = [], []\n",
    "        work_in_left, work_in_right = [], []\n",
    "        for i in range(k):\n",
    "            heappush(wait_in_left, -i)\n",
    "        while 1:\n",
    "            while work_in_left:\n",
    "                t, i = work_in_left[0]\n",
    "                if t > cur:\n",
    "                    break\n",
    "                heappop(work_in_left)\n",
    "                heappush(wait_in_left, -i)\n",
    "            while work_in_right:\n",
    "                t, i = work_in_right[0]\n",
    "                if t > cur:\n",
    "                    break\n",
    "                heappop(work_in_right)\n",
    "                heappush(wait_in_right, -i)\n",
    "            left_to_go = n > 0 and wait_in_left\n",
    "            right_to_go = bool(wait_in_right)\n",
    "            if not left_to_go and not right_to_go:\n",
    "                nxt = inf\n",
    "                if work_in_left:\n",
    "                    nxt = min(nxt, work_in_left[0][0])\n",
    "                if work_in_right:\n",
    "                    nxt = min(nxt, work_in_right[0][0])\n",
    "                cur = nxt\n",
    "                continue\n",
    "            if right_to_go:\n",
    "                i = -heappop(wait_in_right)\n",
    "                cur += time[i][2]\n",
    "                if n == 0 and not wait_in_right and not work_in_right:\n",
    "                    return cur\n",
    "                heappush(work_in_left, (cur + time[i][3], i))\n",
    "            else:\n",
    "                i = -heappop(wait_in_left)\n",
    "                cur += time[i][0]\n",
    "                n -= 1\n",
    "                heappush(work_in_right, (cur + time[i][1], i))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:\n",
    "        time.sort(key=lambda x: x[0] + x[2])\n",
    "        cur = 0\n",
    "        wait_in_left, wait_in_right = [], []\n",
    "        work_in_left, work_in_right = [], []\n",
    "        for i in range(k):\n",
    "            heappush(wait_in_left, -i)\n",
    "        while 1:\n",
    "            while work_in_left:\n",
    "                t, i = work_in_left[0]\n",
    "                if t > cur:\n",
    "                    break\n",
    "                heappop(work_in_left)\n",
    "                heappush(wait_in_left, -i)\n",
    "            while work_in_right:\n",
    "                t, i = work_in_right[0]\n",
    "                if t > cur:\n",
    "                    break\n",
    "                heappop(work_in_right)\n",
    "                heappush(wait_in_right, -i)\n",
    "            left_to_go = n > 0 and wait_in_left\n",
    "            right_to_go = bool(wait_in_right)\n",
    "            if not left_to_go and not right_to_go:\n",
    "                nxt = inf\n",
    "                if work_in_left:\n",
    "                    nxt = min(nxt, work_in_left[0][0])\n",
    "                if work_in_right:\n",
    "                    nxt = min(nxt, work_in_right[0][0])\n",
    "                cur = nxt\n",
    "                continue\n",
    "            if right_to_go:\n",
    "                i = -heappop(wait_in_right)\n",
    "                cur += time[i][2]\n",
    "                if n == 0 and not wait_in_right and not work_in_right:\n",
    "                    return cur\n",
    "                heappush(work_in_left, (cur + time[i][3], i))\n",
    "            else:\n",
    "                i = -heappop(wait_in_left)\n",
    "                cur += time[i][0]\n",
    "                n -= 1\n",
    "                heappush(work_in_right, (cur + time[i][1], i))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:\n",
    "        time.sort(key=lambda x: x[0] + x[2])\n",
    "        cur = 0\n",
    "        wait_in_left, wait_in_right = [], []\n",
    "        work_in_left, work_in_right = [], []\n",
    "        for i in range(k):\n",
    "            heappush(wait_in_left, -i)\n",
    "        while 1:\n",
    "            while work_in_left:\n",
    "                t, i = work_in_left[0]\n",
    "                if t > cur:\n",
    "                    break\n",
    "                heappop(work_in_left)\n",
    "                heappush(wait_in_left, -i)\n",
    "            while work_in_right:\n",
    "                t, i = work_in_right[0]\n",
    "                if t > cur:\n",
    "                    break\n",
    "                heappop(work_in_right)\n",
    "                heappush(wait_in_right, -i)\n",
    "            left_to_go = n > 0 and wait_in_left\n",
    "            right_to_go = bool(wait_in_right)\n",
    "            if not left_to_go and not right_to_go:\n",
    "                nxt = inf\n",
    "                if work_in_left:\n",
    "                    nxt = min(nxt, work_in_left[0][0])\n",
    "                if work_in_right:\n",
    "                    nxt = min(nxt, work_in_right[0][0])\n",
    "                cur = nxt\n",
    "                continue\n",
    "            if right_to_go:\n",
    "                i = -heappop(wait_in_right)\n",
    "                cur += time[i][2]\n",
    "                if n == 0 and not wait_in_right and not work_in_right:\n",
    "                    return cur\n",
    "                heappush(work_in_left, (cur + time[i][3], i))\n",
    "            else:\n",
    "                i = -heappop(wait_in_left)\n",
    "                cur += time[i][0]\n",
    "                n -= 1\n",
    "                heappush(work_in_right, (cur + time[i][1], i))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:\n",
    "        # 根据时间进行排序，sort默认值相同时，下标大的放后。\n",
    "        # 根据题目规则，过桥时间相同的下标大的效率低，因此效率低的就会放后。\n",
    "        # 而过桥时间不同的，时间大的效率低。而前面确定了效率低的放后，说明时间大的要放后，因此对时间进行升序排序\n",
    "        # 排序后效率低的编号大，根据下标即可确定工人的效率高低\n",
    "        time.sort(key=lambda t: t[0] + t[2]) \n",
    "        # 初始化\n",
    "        currTime, remain = 0, n\n",
    "        waitLefts = [-i for i in range(k - 1, -1, -1)]    # 初始化左岸等待队列，效率低的优先，因此倒序遍历工人编号。由于进行大顶堆排序需要使用负号进行改变排序方向，因此引入负号\n",
    "        waitRights = []\n",
    "        workLefts = []\n",
    "        workRights = []\n",
    "        # 只要还有剩余箱子或者右岸还有工人，就模拟搬运\n",
    "        while remain > 0 or waitRights or workRights:\n",
    "            # 1. 若 workLeft 或 workRight 中的工人完成工作，则将他们取出，并分别放置到 waitLeft 和 waitRight 中。\n",
    "            while workLefts and workLefts[0][0] <= currTime:\n",
    "                p = heapq.heappop(workLefts)         # 返回一个左岸完成工作的工人, p = [finishTime, i]\n",
    "                heapq.heappush(waitLefts, -p[1])    # 将完成工作的工人加入左岸等待队列，且效率低在堆顶。由于效率低的编号大，因此要实现的是大顶堆，编号之前加入负号实现\n",
    "            while workRights and workRights[0][0] <= currTime:\n",
    "                p = heapq.heappop(workRights)         # 返回一个右岸完成工作的工人, p = [finishTime, i]\n",
    "                heapq.heappush(waitRights, -p[1])    # 将完成工作的工人加入右岸等待队列\n",
    "            if waitRights:\n",
    "                # 2.若右侧有工人在等待，则取出优先级最低的工人并过桥\n",
    "                i = -heapq.heappop(waitRights)\n",
    "                currTime += time[i][2]  #  更新当前时刻，当前时刻 + 右到左的过桥时间\n",
    "                heapq.heappush(workLefts, [currTime + time[i][3], i])   # 右到左的工人完成时间为到达左岸时刻 + 放下箱子的时间\n",
    "            elif remain > 0 and waitLefts:\n",
    "                # 3. 若右侧还有箱子，并且左侧有工人在等待，则取出优先级最低的工人并过桥\n",
    "                i = -heapq.heappop(waitLefts)\n",
    "                currTime += time[i][0]  #  更新当前时刻，当前时刻 + 左到右的过桥时间\n",
    "                heapq.heappush(workRights, [currTime + time[i][1], i])   # 左到右的工人完成时间为到达右岸时刻 + 搬起箱子的时间\n",
    "                remain -= 1     # 过去一个工人剩余箱子数就减1\n",
    "            else:\n",
    "                # 4. 否则，没有人需要过桥，时间过渡到 workLeft 和 workRight 中的最早完成时间\n",
    "                nextTime = sys.maxsize\n",
    "                if workLefts:\n",
    "                    nextTime = min(nextTime, workLefts[0][0])   # 查看workLefts堆顶元素workLefts[0]\n",
    "                if workRights:\n",
    "                    nextTime = min(nextTime, workRights[0][0])  # 查看workRights堆顶元素workRights[0]\n",
    "                if nextTime != sys.maxsize:\n",
    "                    currTime = max(currTime, nextTime)\n",
    "        return currTime\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:\n",
    "        time.sort(key=lambda x: x[0] + x[2])\n",
    "        cur = 0\n",
    "        wait_in_left, wait_in_right = [], []\n",
    "        work_in_left, work_in_right = [], []\n",
    "        for i in range(k):\n",
    "            heappush(wait_in_left, -i)\n",
    "        while 1:\n",
    "            while work_in_left:\n",
    "                t, i = work_in_left[0]\n",
    "                if t > cur:\n",
    "                    break\n",
    "                heappop(work_in_left)\n",
    "                heappush(wait_in_left, -i)\n",
    "            while work_in_right:\n",
    "                t, i = work_in_right[0]\n",
    "                if t > cur:\n",
    "                    break\n",
    "                heappop(work_in_right)\n",
    "                heappush(wait_in_right, -i)\n",
    "            left_to_go = n > 0 and wait_in_left\n",
    "            right_to_go = bool(wait_in_right)\n",
    "            if not left_to_go and not right_to_go:\n",
    "                nxt = inf\n",
    "                if work_in_left:\n",
    "                    nxt = min(nxt, work_in_left[0][0])\n",
    "                if work_in_right:\n",
    "                    nxt = min(nxt, work_in_right[0][0])\n",
    "                cur = nxt\n",
    "                continue\n",
    "            if right_to_go:\n",
    "                i = -heappop(wait_in_right)\n",
    "                cur += time[i][2]\n",
    "                if n == 0 and not wait_in_right and not work_in_right:\n",
    "                    return cur\n",
    "                heappush(work_in_left, (cur + time[i][3], i))\n",
    "            else:\n",
    "                i = -heappop(wait_in_left)\n",
    "                cur += time[i][0]\n",
    "                n -= 1\n",
    "                heappush(work_in_right, (cur + time[i][1], i))\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:\n",
    "        time.sort(key = lambda x: x[0] + x [2])\n",
    "        workL, workR, waitR = [], [], []\n",
    "        waitL = [[-i,0] for i in range(k)]\n",
    "        heapq.heapify(waitL)\n",
    "        #工作队列按时间从小到大排序，因此（时间，下标）\n",
    "        #等待队列按效率，即工人下标从大到小排序，因此（下标，时间）\n",
    "        cur = 0\n",
    "\n",
    "        while n:\n",
    "            while workL and workL[0][0] <= cur:\n",
    "                p = heapq.heappop(workL)\n",
    "                p[0], p[1] = p[1], p[0]\n",
    "                heapq.heappush(waitL,p)\n",
    "                #弹出左边完成工作的，压入左边等待队列\n",
    "            \n",
    "            while workR and workR[0][0] <= cur:\n",
    "                p = heapq.heappop(workR)\n",
    "                p[0], p[1] = p[1], p[0]\n",
    "                heapq.heappush(waitR,p)\n",
    "                #弹出右边完成工作的，压入右边等待队列\n",
    "            \n",
    "            ###接下来决定时间的流逝，过河\n",
    "            if waitR: #右边先过\n",
    "                p = heapq.heappop(waitR)\n",
    "                cur += time[- p[0]][2]\n",
    "                p[1] = p[0]\n",
    "                p[0] = cur + time[-p[0]][3] #时间增量为过河加工作\n",
    "                heapq.heappush(workL,p) #加入左边的工作队列\n",
    "            elif waitL:\n",
    "                p = heapq.heappop(waitL)\n",
    "                cur += time[- p[0]][0]\n",
    "                p[1] = p[0]\n",
    "                p[0] = cur + time[-p[0]][1] #时间增量为过河加工作\n",
    "                heapq.heappush(workR,p) #加入右边的工作队列\n",
    "                n -= 1 #箱子被拿\n",
    "            #如果此时两边等待队列都为空，让时间快进到某一边率先干完\n",
    "            elif len(workL) == 0:\n",
    "                cur = workR[0][0]\n",
    "            elif len(workR) == 0:\n",
    "                cur = workL[0][0]\n",
    "            else:\n",
    "                cur = min(workL[0][0],workR[0][0])\n",
    "        #n减为0时，时间停在最后一个要搬箱的工人过桥到达右边开始工作的时刻\n",
    "        #虽然时间变化了，但是等待队列并没有更新，也就说waitR是空的\n",
    "        while workR:\n",
    "            p = heapq.heappop(workR)\n",
    "            cur = max(p[0],cur) + time[- p[1]][2]\n",
    "        #要么工作要么等待，加上过桥时间\n",
    "        return cur\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:\n",
    "        ql = []\n",
    "        qr = []\n",
    "        qlw = []\n",
    "        qrw = []\n",
    "\n",
    "        for i, (lr, po, rl, pn) in enumerate(time):\n",
    "            heappush(ql, (-lr - rl, -i))\n",
    "\n",
    "        remain = n\n",
    "        t = 0\n",
    "\n",
    "        while remain > 0 or qr or qrw:\n",
    "            while qrw and qrw[0][0] <= t:\n",
    "                _, ii = heappop(qrw)\n",
    "                lr, po, rl, pn = time[-ii]\n",
    "                heappush(qr, (-lr - rl, ii))\n",
    "\n",
    "            while qlw and qlw[0][0] <= t:\n",
    "                _, ii = heappop(qlw)\n",
    "                lr, po, rl, pn = time[-ii]\n",
    "                heappush(ql, (-lr - rl, ii))\n",
    "\n",
    "            if qr:\n",
    "                e, ii = heappop(qr)\n",
    "                lr, po, rl, pn = time[-ii]\n",
    "                heappush(qlw, (t + rl + pn, ii))\n",
    "                t += rl\n",
    "            elif ql and remain > 0 and not qr:\n",
    "                e, ii = heappop(ql)\n",
    "                lr, po, rl, pn = time[-ii]\n",
    "                heappush(qrw, (t + lr + po, ii))\n",
    "                t += lr\n",
    "                remain -= 1\n",
    "            else:\n",
    "                if qrw and qlw:\n",
    "                    t = min(qrw[0][0], qlw[0][0])\n",
    "                elif qrw:\n",
    "                    t = qrw[0][0]\n",
    "                elif qlw:\n",
    "                    t = qlw[0][0]\n",
    "\n",
    "        return t\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:\n",
    "        time.sort(key=lambda t: t[0] + t[2])  # 稳定排序\n",
    "        cur = 0\n",
    "        workL, waitL, waitR, workR = [], [[-i, 0] for i in range(k - 1, -1, -1)], [], []  # 下标越大效率越低\n",
    "        while n:\n",
    "            while workL and workL[0][0] <= cur:\n",
    "                p = heappop(workL)\n",
    "                p[0], p[1] = p[1], p[0]\n",
    "                heappush(waitL, p)  # 左边完成放箱\n",
    "            while workR and workR[0][0] <= cur:\n",
    "                p = heappop(workR)\n",
    "                p[0], p[1] = p[1], p[0]\n",
    "                heappush(waitR, p)  # 右边完成搬箱\n",
    "            if waitR:  # 右边过桥，注意加到 waitR 中的都是 <= cur 的（下同）\n",
    "                p = heappop(waitR)\n",
    "                cur += time[-p[0]][2]\n",
    "                p[1] = p[0]\n",
    "                p[0] = cur + time[-p[0]][3]\n",
    "                heappush(workL, p)  # 放箱\n",
    "            elif waitL:  # 左边过桥\n",
    "                p = heappop(waitL)\n",
    "                cur += time[-p[0]][0]\n",
    "                p[1] = p[0]\n",
    "                p[0] = cur + time[-p[0]][1]\n",
    "                heappush(workR, p)  # 搬箱\n",
    "                n -= 1\n",
    "            elif len(workL) == 0: cur = workR[0][0]  # cur 过小，找个最小的放箱/搬箱完成时间来更新 cur\n",
    "            elif len(workR) == 0: cur = workL[0][0]\n",
    "            else: cur = min(workL[0][0], workR[0][0])\n",
    "        while workR:\n",
    "            t, i = heappop(workR)  # 右边完成搬箱\n",
    "            # 如果没有排队，直接过桥；否则由于无论谁先过桥，最终完成时间都一样，所以也可以直接计算\n",
    "            cur = max(t, cur) + time[-i][2]\n",
    "        return cur  # 最后一个过桥的时间\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:\n",
    "        # 优先队列模拟\n",
    "        time.sort(key=lambda t: t[0] + t[2])  # 稳定排序\n",
    "        cur = 0\n",
    "        workL, waitL, waitR, workR = [], [[-i, 0] for i in range(k - 1, -1, -1)], [], []  # 下标越大效率越低\n",
    "        while n:\n",
    "            while workL and workL[0][0] <= cur:\n",
    "                p = heappop(workL)\n",
    "                p[0], p[1] = p[1], p[0]\n",
    "                heappush(waitL, p)  # 左边完成放箱\n",
    "            while workR and workR[0][0] <= cur:\n",
    "                p = heappop(workR)\n",
    "                p[0], p[1] = p[1], p[0]\n",
    "                heappush(waitR, p)  # 右边完成搬箱\n",
    "            if waitR:  # 右边过桥，注意加到 waitR 中的都是 <= cur 的（下同）\n",
    "                p = heappop(waitR)\n",
    "                cur += time[-p[0]][2]\n",
    "                p[1] = p[0]\n",
    "                p[0] = cur + time[-p[0]][3]\n",
    "                heappush(workL, p)  # 放箱\n",
    "            elif waitL:  # 左边过桥\n",
    "                p = heappop(waitL)\n",
    "                cur += time[-p[0]][0]\n",
    "                p[1] = p[0]\n",
    "                p[0] = cur + time[-p[0]][1]\n",
    "                heappush(workR, p)  # 搬箱\n",
    "                n -= 1\n",
    "            elif len(workL) == 0: cur = workR[0][0]  # cur 过小，找个最小的放箱/搬箱完成时间来更新 cur\n",
    "            elif len(workR) == 0: cur = workL[0][0]\n",
    "            else: cur = min(workL[0][0], workR[0][0])\n",
    "        while workR:\n",
    "            t, i = heappop(workR)  # 右边完成搬箱\n",
    "            # 如果没有排队，直接过桥；否则由于无论谁先过桥，最终完成时间都一样，所以也可以直接计算\n",
    "            cur = max(t, cur) + time[-i][2]\n",
    "        return cur  # 最后一个过桥的时间\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int: \n",
    "        # 1. O(k) initialize 4 heaps\n",
    "        workL = []  # min-heap, workers at the new warehouse putting boxes, element: (finish time of putting a box, worker id), priority: finish time ascendingly\n",
    "        workR = []  # min-heap, workers at the old warehouse picking boxes, element: (finish time of picking a box, worker id), priority: finish time ascendingly\n",
    "\n",
    "        waitL = [[-(leftToRight+rightToLeft), -i] for i, (leftToRight, pickOld, rightToLeft, putNew) in enumerate(time)]  \n",
    "        heapify(waitL)   \n",
    "        # max-heap, workers waiting at the left bank of the bridge, element: [cross time, worker id], priority: efficiency ascendingly\n",
    "        # initially all the k workers are waiting at the left bank of the bridge\n",
    "        waitR = []  # max-heap, workers waiting at the right bank of the bridge, element: [cross time, worker id], priority: efficiency ascendingly\n",
    "\n",
    "        # 2. O(nlogk) iterates until workers have crossed the bridge for n times in total\n",
    "        t = 0   # starting timestamp\n",
    "        while n or workR or waitR:\n",
    "            # (1) O(logk) workers finish putting boxes then wait at the left bank of the bridge\n",
    "            while workL and workL[0][0] <= t:\n",
    "                endTime, idx = heappop(workL)\n",
    "                leftToRight, pickOld, rightToLeft, putNew = time[-idx]\n",
    "                heappush(waitL, [-(leftToRight+rightToLeft), idx])\n",
    "            \n",
    "            # (2) O(logk) workers finish picking boxes then wait at the right bank of the bridge\n",
    "            while workR and workR[0][0] <= t:\n",
    "                endTime, idx = heappop(workR)\n",
    "                leftToRight, pickOld, rightToLeft, putNew = time[-idx]\n",
    "                heappush(waitR, [-(leftToRight+rightToLeft), idx])\n",
    "            \n",
    "            # a worker crosses the bridge\n",
    "            # priority: worker over the bridge > worker waiting on the right with lowest efficiency > worker waiting on the left with lowest efficiency\n",
    "\n",
    "            # a worker waiting at right bank crosses the bridge\n",
    "            if waitR:\n",
    "                crossTime, idx = heappop(waitR)\n",
    "                leftToRight, pickOld, rightToLeft, putNew = time[-idx]\n",
    "                t += rightToLeft\n",
    "                heappush(workL, [t + putNew, idx])\n",
    "            \n",
    "            # a worker waiting at left bank crosses the bridge           \n",
    "            elif n and waitL:\n",
    "                crossTime, idx = heappop(waitL)\n",
    "                leftToRight, pickOld, rightToLeft, putNew = time[-idx]\n",
    "                t += leftToRight\n",
    "                heappush(workR, [t+pickOld, idx])\n",
    "                n -= 1\n",
    "\n",
    "            # if no worker is waiting, fast forward to the earliest finish time of putting/picking a box\n",
    "            else:\n",
    "                earlistEndTime = math.inf \n",
    "                if workL:\n",
    "                    earlistEndTime = min(earlistEndTime, workL[0][0])\n",
    "                if workR:\n",
    "                    earlistEndTime = min(earlistEndTime, workR[0][0])\n",
    "                if earlistEndTime != math.inf:\n",
    "                    t = max(t, earlistEndTime)\n",
    "        \n",
    "        \n",
    "        return t  # 最后一个过桥的时间\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int: \n",
    "        # 1. O(k) initialize 4 heaps\n",
    "        workL = []  # min-heap, workers at the new warehouse putting boxes, element: (finish time of putting a box, worker id), priority: finish time ascendingly\n",
    "        workR = []  # min-heap, workers at the old warehouse picking boxes, element: (finish time of picking a box, worker id), priority: finish time ascendingly\n",
    "\n",
    "        waitL = [[-(leftToRight+rightToLeft), -i] for i, (leftToRight, pickOld, rightToLeft, putNew) in enumerate(time)]  \n",
    "        heapify(waitL)   \n",
    "        # max-heap, workers waiting at the left bank of the bridge, element: [cross time, worker id], priority: efficiency ascendingly\n",
    "        # initially all the k workers are waiting at the left bank of the bridge\n",
    "        waitR = []  # max-heap, workers waiting at the right bank of the bridge, element: [cross time, worker id], priority: efficiency ascendingly\n",
    "\n",
    "        # 2. O(nlogk) iterates until workers have crossed the bridge for n times in total\n",
    "        t = 0   # starting timestamp\n",
    "        while n or workR or waitR:\n",
    "            # (1) O(logk) workers finish putting boxes then wait at the left bank of the bridge\n",
    "            while workL and workL[0][0] <= t:\n",
    "                endTime, idx = heappop(workL)\n",
    "                leftToRight, pickOld, rightToLeft, putNew = time[-idx]\n",
    "                heappush(waitL, [-(leftToRight+rightToLeft), idx])\n",
    "            \n",
    "            # (2) O(logk) workers finish picking boxes then wait at the right bank of the bridge\n",
    "            while workR and workR[0][0] <= t:\n",
    "                endTime, idx = heappop(workR)\n",
    "                leftToRight, pickOld, rightToLeft, putNew = time[-idx]\n",
    "                heappush(waitR, [-(leftToRight+rightToLeft), idx])\n",
    "            \n",
    "            # a worker crosses the bridge\n",
    "            # priority: worker over the bridge > worker waiting on the right with lowest efficiency > worker waiting on the left with lowest efficiency\n",
    "\n",
    "            # a worker waiting at right bank crosses the bridge\n",
    "            if waitR:\n",
    "                crossTime, idx = heappop(waitR)\n",
    "                leftToRight, pickOld, rightToLeft, putNew = time[-idx]\n",
    "                t += rightToLeft\n",
    "                heappush(workL, [t + putNew, idx])\n",
    "            \n",
    "            # a worker waiting at left bank crosses the bridge           \n",
    "            elif n and waitL:\n",
    "                crossTime, idx = heappop(waitL)\n",
    "                leftToRight, pickOld, rightToLeft, putNew = time[-idx]\n",
    "                t += leftToRight\n",
    "                heappush(workR, [t+pickOld, idx])\n",
    "                n -= 1\n",
    "\n",
    "            # if no worker is waiting, fast forward to the earliest finish time of putting/picking a box\n",
    "            else:\n",
    "                if not workL:\n",
    "                    t = workR[0][0]\n",
    "                elif not workR:\n",
    "                    t = workL[0][0]\n",
    "                else:\n",
    "                    t = min(workR[0][0], workL[0][0])\n",
    "        \n",
    "        \n",
    "        return t  # 最后一个过桥的时间\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int: \n",
    "        # 1. O(k) initialize 4 heaps\n",
    "        workL = []  # min-heap, workers at the new warehouse putting boxes, element: (finish time of putting a box, worker id), priority: finish time ascendingly\n",
    "        workR = []  # min-heap, workers at the old warehouse picking boxes, element: (finish time of picking a box, worker id), priority: finish time ascendingly\n",
    "\n",
    "        waitL = [[-(leftToRight+rightToLeft), -i] for i, (leftToRight, pickOld, rightToLeft, putNew) in enumerate(time)]  \n",
    "        heapify(waitL)   \n",
    "        # max-heap, workers waiting at the left bank of the bridge, element: [cross time, worker id], priority: efficiency ascendingly\n",
    "        # initially all the k workers are waiting at the left bank of the bridge\n",
    "        waitR = []  # max-heap, workers waiting at the right bank of the bridge, element: [cross time, worker id], priority: efficiency ascendingly\n",
    "\n",
    "        # 2. O(nlogk) iterates until workers have crossed the bridge for n times in total\n",
    "        t = 0   # starting timestamp\n",
    "        while n or workR or waitR:\n",
    "            # (1) O(logk) workers finish putting boxes then wait at the left bank of the bridge\n",
    "            while workL and workL[0][0] <= t:\n",
    "                endTime, idx = heappop(workL)\n",
    "                leftToRight, pickOld, rightToLeft, putNew = time[-idx]\n",
    "                heappush(waitL, [-(leftToRight+rightToLeft), idx])\n",
    "            \n",
    "            # (2) O(logk) workers finish picking boxes then wait at the right bank of the bridge\n",
    "            while workR and workR[0][0] <= t:\n",
    "                endTime, idx = heappop(workR)\n",
    "                leftToRight, pickOld, rightToLeft, putNew = time[-idx]\n",
    "                heappush(waitR, [-(leftToRight+rightToLeft), idx])\n",
    "            \n",
    "            # a worker crosses the bridge\n",
    "            # priority: worker over the bridge > worker waiting on the right with lowest efficiency > worker waiting on the left with lowest efficiency\n",
    "\n",
    "            # a worker waiting at right bank crosses the bridge\n",
    "            if waitR:\n",
    "                crossTime, idx = heappop(waitR)\n",
    "                leftToRight, pickOld, rightToLeft, putNew = time[-idx]\n",
    "                t += rightToLeft\n",
    "                heappush(workL, [t + putNew, idx])\n",
    "            \n",
    "            # a worker waiting at left bank crosses the bridge           \n",
    "            elif n and waitL:\n",
    "                crossTime, idx = heappop(waitL)\n",
    "                leftToRight, pickOld, rightToLeft, putNew = time[-idx]\n",
    "                t += leftToRight\n",
    "                heappush(workR, [t+pickOld, idx])\n",
    "                n -= 1\n",
    "\n",
    "            # if no worker is waiting, fast forward to the earliest finish time of putting/picking a box\n",
    "            else:\n",
    "                earlistEndTime = math.inf \n",
    "                if workL:\n",
    "                    earlistEndTime = min(earlistEndTime, workL[0][0])\n",
    "                if workR:\n",
    "                    earlistEndTime = min(earlistEndTime, workR[0][0])\n",
    "                if earlistEndTime != math.inf:\n",
    "                    t = earlistEndTime\n",
    "        \n",
    "        \n",
    "        return t  # 最后一个过桥的时间\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:\n",
    "        time.sort(key=lambda t: t[0] + t[2])  # 稳定排序\n",
    "        cur = 0\n",
    "        workL, waitL, waitR, workR = [], [[-i, 0] for i in range(k - 1, -1, -1)], [], []  # 下标越大效率越低\n",
    "        while n:\n",
    "            while workL and workL[0][0] <= cur:\n",
    "                p = heappop(workL)\n",
    "                p[0], p[1] = p[1], p[0]\n",
    "                heappush(waitL, p)  # 左边完成放箱\n",
    "            while workR and workR[0][0] <= cur:\n",
    "                p = heappop(workR)\n",
    "                p[0], p[1] = p[1], p[0]\n",
    "                heappush(waitR, p)  # 右边完成搬箱\n",
    "            if waitR:  # 右边过桥，注意加到 waitR 中的都是 <= cur 的（下同）\n",
    "                p = heappop(waitR)\n",
    "                cur += time[-p[0]][2]\n",
    "                p[1] = p[0]\n",
    "                p[0] = cur + time[-p[0]][3]\n",
    "                heappush(workL, p)  # 放箱\n",
    "            elif waitL:  # 左边过桥\n",
    "                p = heappop(waitL)\n",
    "                cur += time[-p[0]][0]\n",
    "                p[1] = p[0]\n",
    "                p[0] = cur + time[-p[0]][1]\n",
    "                heappush(workR, p)  # 搬箱\n",
    "                n -= 1\n",
    "            elif len(workL) == 0: cur = workR[0][0]  # cur 过小，找个最小的放箱/搬箱完成时间来更新 cur\n",
    "            elif len(workR) == 0: cur = workL[0][0]\n",
    "            else: cur = min(workL[0][0], workR[0][0])\n",
    "        while workR:\n",
    "            t, i = heappop(workR)  # 右边完成搬箱\n",
    "            # 如果没有排队，直接过桥；否则由于无论谁先过桥，最终完成时间都一样，所以也可以直接计算\n",
    "            cur = max(t, cur) + time[-i][2]\n",
    "        return cur  # 最后一个过桥的时间\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:\n",
    "        tflag=0\n",
    "        rsflag=0\n",
    "        boxflag=0\n",
    "        ret=0\n",
    "        idxl=[]\n",
    "        llp=[]\n",
    "        llq=[]\n",
    "        rrp=[]\n",
    "        rrq=[]\n",
    "        \n",
    "        for i in range(k):\n",
    "            idxl.append((-1)*(time[i][0]+time[i][2]))\n",
    "            heapq.heappush(llp,[0,(-1)*(time[i][0]+time[i][2]),-i,i])\n",
    "\n",
    "        while True:\n",
    "            while len(llq)>0 and llq[0][0]<=tflag:\n",
    "                tm,xl,id1,id=heapq.heappop(llq)\n",
    "                heapq.heappush(llp,[0,idxl[id],-id,id])\n",
    "            while len(rrp)>0 and rrp[0][0]<=tflag:\n",
    "                tm,xl,id1,id=heapq.heappop(rrp)\n",
    "                heapq.heappush(rrq,[0,idxl[id],-id,id])\n",
    "\n",
    "            xtm=-1\n",
    "            if len(rrq)>0:\n",
    "                tm,xl,id1,id=heapq.heappop(rrq)\n",
    "                heapq.heappush(llq,[tflag+time[id][2]+time[id][3],idxl[id],-id,id])\n",
    "                if tflag+time[id][2]>ret:\n",
    "                    ret=tflag+time[id][2]\n",
    "                rsflag+=1\n",
    "                if rsflag==n:\n",
    "                    return ret\n",
    "                xtm=time[id][2]\n",
    "            elif len(llp)>0 and boxflag<n:\n",
    "                tm,xl,id1,id=heapq.heappop(llp)\n",
    "                heapq.heappush(rrp,[tflag+time[id][0]+time[id][1],idxl[id],-id,id])\n",
    "                boxflag+=1\n",
    "                xtm=time[id][0]\n",
    "            else:\n",
    "                if len(llq)>0 and boxflag<n :\n",
    "                    xtm=llq[0][0]\n",
    "                if len(rrp)>0 and (xtm==-1 or xtm>rrp[0][0]):\n",
    "                    xtm=rrp[0][0]\n",
    "                if xtm==-1:\n",
    "                    xtm=tflag+1\n",
    "                tflag=xtm\n",
    "                continue\n",
    "            tflag+=xtm\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:\n",
    "        tflag=0\n",
    "        rsflag=0\n",
    "        boxflag=0\n",
    "        ret=0\n",
    "        idxl=[]\n",
    "        llp=[]\n",
    "        llq=[]\n",
    "        rrp=[]\n",
    "        rrq=[]\n",
    "        \n",
    "        for i in range(k):\n",
    "            idxl.append((-1)*(time[i][0]+time[i][2]))\n",
    "            heapq.heappush(llp,[0,(-1)*(time[i][0]+time[i][2]),-i,i])\n",
    "\n",
    "        while True:\n",
    "            while len(llq)>0 and llq[0][0]<=tflag:\n",
    "                tm,xl,id1,id=heapq.heappop(llq)\n",
    "                heapq.heappush(llp,[0,idxl[id],-id,id])\n",
    "            while len(rrp)>0 and rrp[0][0]<=tflag:\n",
    "                tm,xl,id1,id=heapq.heappop(rrp)\n",
    "                heapq.heappush(rrq,[0,idxl[id],-id,id])\n",
    "\n",
    "            #print(tflag)\n",
    "            #print(llp,rrp,rrq,llq)\n",
    "            xtm=-1\n",
    "            if len(rrq)>0:\n",
    "                tm,xl,id1,id=heapq.heappop(rrq)\n",
    "                heapq.heappush(llq,[tflag+time[id][2]+time[id][3],idxl[id],-id,id])\n",
    "                if tflag+time[id][2]>ret:\n",
    "                    ret=tflag+time[id][2]\n",
    "                rsflag+=1\n",
    "                if rsflag==n:\n",
    "                    return ret\n",
    "                xtm=time[id][2]\n",
    "            elif len(llp)>0 and boxflag<n:\n",
    "                tm,xl,id1,id=heapq.heappop(llp)\n",
    "                heapq.heappush(rrp,[tflag+time[id][0]+time[id][1],idxl[id],-id,id])\n",
    "                boxflag+=1\n",
    "                xtm=time[id][0]\n",
    "            else:\n",
    "                xtm=1\n",
    "            tflag+=xtm\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:\n",
    "        idx2eff = []\n",
    "        for idx, (l2r, _, r2l, _) in enumerate(time):\n",
    "            idx2eff.append((-l2r - r2l, -idx))\n",
    "\n",
    "        # def cmp(x, y):\n",
    "        #     t1, idx1 = idx2eff[x]\n",
    "        #     t2, idx2 = idx2eff[y]\n",
    "        #     if t1 == t2:\n",
    "        #         return idx1 > idx2\n",
    "        #     return t1 > t2\n",
    "\n",
    "        hOld = []\n",
    "        hNew = []\n",
    "        cur = 0\n",
    "        for idx in range(k):\n",
    "            heapq.heappush(hNew, (cur, idx2eff[idx], idx))\n",
    "\n",
    "        l = r = 0\n",
    "        candOld, candNew = [], []\n",
    "\n",
    "        def old_faster():\n",
    "            return hOld[0][0] <= hNew[0][0]\n",
    "\n",
    "        while l < n:\n",
    "            while len(hOld) > 0 and \\\n",
    "            (\n",
    "                hOld[0][0] <= cur or \\\n",
    "                (len(candNew) == 0 and \\\n",
    "                (len(hNew) == 0 or hOld[0][0] <= hNew[0][0])) or \\\n",
    "                r >= n\n",
    "            ):\n",
    "                if hOld[0][0] <= cur:\n",
    "                    # print(\"back1:\", cur)\n",
    "                    heapq.heappush(candOld, heapq.heappop(hOld)[1:])\n",
    "                    while len(candOld) > 0:\n",
    "                        while len(hOld) > 0 and hOld[0][0] <= cur:\n",
    "                            heapq.heappush(candOld, heapq.heappop(hOld)[1:])\n",
    "                        # tmp = heapq.heappop(cand)\n",
    "                        # print(tmp)\n",
    "                        # e, idx = tmp\n",
    "                        e, idx = heapq.heappop(candOld)\n",
    "                        # print(\"idx:\",idx)\n",
    "                        l2r, po, r2l, pn = time[idx]\n",
    "                        cur += r2l\n",
    "                        heapq.heappush(hNew, (cur + pn, e, idx))\n",
    "                        l += 1\n",
    "                        if l >= n:\n",
    "                            return cur\n",
    "                else:\n",
    "                    # print(\"back2:\", cur)\n",
    "                    t, e, idx = heapq.heappop(hOld)\n",
    "                    # print(\"idx:\",idx)\n",
    "                    l2r, po, r2l, pn = time[idx]\n",
    "                    cur = t + r2l\n",
    "                    heapq.heappush(hNew, (cur + pn, e, idx))\n",
    "                    l += 1\n",
    "                    if l >= n:\n",
    "                        return cur\n",
    "            if r >= n:\n",
    "                # print(666)\n",
    "                continue\n",
    "            if len(candNew) > 0 or hNew[0][0] <= cur:\n",
    "                # print(\"go1:\", cur)\n",
    "                if len(hNew) > 0 and hNew[0][0] <= cur:\n",
    "                    heapq.heappush(candNew, heapq.heappop(hNew)[1:])\n",
    "                while (len(hOld) == 0 or cur < hOld[0][0]) and r < n and len(candNew) > 0:\n",
    "                    while len(hNew) > 0 and hNew[0][0] <= cur:\n",
    "                        heapq.heappush(candNew, heapq.heappop(hNew)[1:])\n",
    "                    e, idx = heapq.heappop(candNew)\n",
    "                    # print(\"idx:\",idx)\n",
    "                    l2r, po, r2l, pn = time[idx]\n",
    "                    cur += l2r\n",
    "                    heapq.heappush(hOld, (cur + po, e, idx))\n",
    "                    r += 1\n",
    "                # if r < n:\n",
    "                #     for c in candNew:\n",
    "                #         heapq.heappush(hNew, (cur, *c))\n",
    "            else:\n",
    "                # print(\"go2:\", cur)\n",
    "                t, e, idx = heapq.heappop(hNew)\n",
    "                # print(\"idx:\",idx)\n",
    "                l2r, po, r2l, pn = time[idx]\n",
    "                cur = t + l2r\n",
    "                heapq.heappush(hOld, (cur + po, e, idx))\n",
    "                r += 1\n",
    "        return -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
